package leetcode.editor.cn;

//地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一
//格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但
//它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？ 
//
// 
//
// 示例 1： 
//
// 输入：m = 2, n = 3, k = 1
//输出：3
// 
//
// 示例 2： 
//
// 输入：m = 3, n = 1, k = 0
//输出：1
// 
//
// 提示： 
//
// 
// 1 <= n,m <= 100 
// 0 <= k <= 20 
// 
// 👍 276 👎 0

public class JiQiRenDeYunDongFanWeiLcof{
    public static void main(String[] args) {
        Solution solution = new JiQiRenDeYunDongFanWeiLcof().new Solution();}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int movingCount(int m, int n, int k) {
        /*思路：此处是求最大值，明显是dfs问题。*/
        boolean[][] isVisited = new boolean[m][n];
        //此处明显是从第一个就可以开始利用dfs求解。
        int res = dfs(m,n,k,isVisited,0,0);
        return res;
    }

    /*对于dfs问题，需要有参数，标记访问数组，索引*/
    private int dfs(int m,int n,int k,boolean[][] isVisited,int i,int j){
        //返回条件：错误的情况：索引越界，已访问，和结果不等
        if(i<0 || i==m || j<0 || j==n || isVisited[i][j] || (i%10+i/10+j/10+j%10)>k ){
            return 0;
        }

        /*正确情况：标记访问、采用策略进行下一步(对此进行计数+1;并按dfs方法探索四周)、
         重新标记为未访问（需要回溯时）、返回结果*/
        isVisited[i][j] = true;
            //此处的策略是：按照一定方向试探，将符合规定的结果相加
        int res= dfs(m,n,k,isVisited,i-1,j)+dfs(m,n,k,isVisited,i,j+1)+
                 dfs(m,n,k,isVisited,i+1,j)+dfs(m,n,k,isVisited,i,j-1)+1;
        //由于此处不需要回溯，因此不需要重新标记为未访问;
        /*且对于回溯问题，需要有针对于回溯过程的退出条件*/
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}